package org.xingole.leetcode.dp.multidimension.jump;

import java.util.Arrays;

/**
 * Problem Description:
 * 
 * <a href="https://leetcode.com/problems/frog-jump/description/">Frog Jump</a>
 */
public class FrogJump {

     public boolean canCrossWithDP(int[] stones) {
          int n = stones.length;

          // 1. Determine the subproblem structure
          // dp[i][k]: whether the frog can arrive stone[i] position and the last jump 
          // was k units.(Note k may be so large and we must optimize the space complexity).
          boolean[][] dp = new boolean[n][n];

          // 2. Recursively solve the problem
          //   - Inductive cases:
          //     dp[i][k] = OR(dp[j][h] AND stones[j] + k == stones[i])
          //   where 0 <= j < i, h = k + 1 or k or k - 1.
          //   - Base cases:
          //     dp[0][0] = true
          dp[0][0] = true;

          // 3. Reduntant cases elimination
          //    A. If the frog now is at stone i, then the last jump unit k must satisfy 
          // k <= i.
          //    B. If the distance between stone i and stone i - 1 is greater than  i units,
          // then the frog mustn't arrive the destination.
          // 
          // This idea is to decrease the solution spaces to the only subset solutions 
          // containing the ultimate result.
          for ( int i = 1; i <  n; ++i ) {
               if ( stones[i] - stones[i-1] > i ) {
                    return false;
               }
          }

          // Loop invariant: solve the dp[i][k] according to the topological sort.
          for ( int i = 1; i < n; ++i ) {
               for ( int j = i - 1; j >= 0; --j ) {
                    int k = stones[i] - stones[j];
                    if ( k > j + 1 ) {
                         break;
                    }

                    dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1];
     
                    // we can check the result at here
                    if ( i == n - 1 && dp[i][k] ) {
                         return true;
                    }
               }

          }

          return false;
     }

     public boolean canCrossWithMemo(int[] stones) {
          int n = stones.length;

          Boolean[][] memo = new Boolean[n][n];

          return dfs(stones, 0, 0, memo);
     }

     /**
      * Whether the frog can arrive the destination from stone index and the last jump 
      * was lastJump units. We use the memo array to optimize the time complexity. 
      */
     private boolean dfs(int[] stones, int index, int lastJump, Boolean[][] memo) {

          // Base case: already arriving at the destination.
          if ( index == stones.length - 1 ) {
               return true;
          }

          // This subproblem we have solved, then return the result directly.
          if ( memo[index][lastJump] != null ) {
               return memo[index][lastJump];
          }

          for ( int currJump = lastJump - 1; currJump <= lastJump + 1; currJump++ ) {
               if ( currJump > 0 ) {
                    int nextIndex = Arrays.binarySearch(stones, index, stones.length, currJump + stones[index]);
                    if ( 
                         nextIndex >= 0 && 
                         dfs(stones, nextIndex, currJump, memo) 
                    ) {
                         return memo[index][lastJump] = true;
                    }
               }
          }

          return memo[index][lastJump] = false;
     }

     public static void main(String[] args) {
          var fj = new FrogJump();

          int[] stones;

          // Example 1:
          stones = new int[]{0, 1, 3, 5, 6, 8, 12, 17};
          System.out.println("Example 1 Output: " + fj.canCrossWithDP(stones) );
          System.out.println("Example 1 Expected:  true");

     }

}
